package com.lm.leetcode.str;

/**
 * @Auther: Min.Liu
 * @Description: 问题：  给你一个字符串 s，找到 s 中最长的 回文 子串。
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 * @Date: Created in 14:45 2025/5/8
 */
public class longestPalindromeDemo {
    public static void main(String[] args) {
        longestPalindromeDemo demo = new longestPalindromeDemo();
        System.out.println(demo.longestPalindrome("babccad"));
        System.out.println(demo.longestPalindrome("cbbd"));
        System.out.println(demo.longestPalindrome("aacabdkacaa"));
        System.out.println(demo.longestPalindrome("ccc"));
        System.out.println(demo.longestPalindrome("cc"));
        System.out.println(demo.longestPalindrome("bab"));
        System.out.println(demo.longestPalindrome("baab"));
        System.out.println(demo.isPalindrome("abca"));
    }


    /*
       开始点 start
       距离 distance
       distance 开始为0 找到相同元素
     */
    public String longestPalindrome(String s) {
        int start = 0;
        int distance = 0;
        int index = 0;
        //"babad" "babccad"
        do {
            for (int i = index + 1; i < s.length(); i++) {
//                if (isPalindrome(s.substring(index,i+1))) {
                if (isPalindrome(s, index, i)) {
                    //int max = Math.max(i - index, distance);
                    int max = i - index>distance?i - index:distance;
                    if (distance < max) {
                        distance = max;
                        start = index;
                    }
                }
            }
            if (index < s.length()) {
                index++;
            }
        } while (distance + index < s.length() - 1);

        return s.substring(start, start + distance + 1);
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public boolean isPalindrome(String s) {
        for (int i = 0; i < (s.length() / 2); i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    //"babccad"
    public String longestPalindrome2(String s) {
        int distance = 0; int start = 0;
        for (int i = 0; i < s.length(); i++) {
            //奇数最长回文长度  1
            int len1 = longestLen(s, i, i); //bb bab bddb  aadbb   1  3
            //偶数最长回文长度
            int len2 = longestLen(s, i, i + 1);  //  2
            if (len1 > distance) {//奇
                distance = len1;
                start = i - (distance / 2);
            }
            if (len2 > distance) {//偶
                distance = len2;
                start = i - (distance / 2 );
            }
        }
        return s.substring(start, start + distance+1);
    }

    //从指定位置开始左右探索 最长回文串
    private int longestLen(String s, int left, int right) {
        int dintance = 0;
        if(left==right&&right < s.length() && left >= 0){
            left--;right++;
        }
        while (right < s.length() && left >= 0) {
            if (s.charAt(left) == s.charAt(right)) {
                dintance = right-left;
            }else{
                break;
            }
            left--;right++;
        }
        return dintance;
    }


}
